BOJ_1351_무한 수열

재귀(Recursion)를 사용해서 수열의 값을 구하는 문제

재귀를 떠올렸다가 N이 10¹²인 걸 보고 망설였다

재귀 함수의 시간복잡도를 구할 때는 예시를 적어보고 파악한다고 한다
이 문제의 경우, n을 매번 P나 Q로 나누기 때문에 2라고 가정해도 log로 줄어들게 된다

따라서 연산 횟수가 O(log N)이라고 추측할 수 있고,
이에 따라 재귀 함수를 사용할 수 있다

from collections import defaultdict  
  
N, P, Q = map(int, input().split())  
  
num1 = 1  
num2 = 1  
  
def dfs(n, p, q, memo):  
    if memo[n] > 0:  
        return memo[n]  
  
    memo[n] = dfs(n // p, p, q, memo) + dfs(n // q, p, q, memo)  
    return memo[n]  
  
  
memo = defaultdict(int)  
memo[0] = 1  
  
res = dfs(N, P, Q, memo)  
print(res)